package test_0523;

public class test05_binary_search {
    public static void main(String[] args) {
        int[] arr = new int[1000000000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i + 1;
        }
        int findNum = 13200;
//        //传统方法,用时437ms
//        long start = System.currentTimeMillis();
//        for (int i = 0; i < arr.length - 1; i++) {
//            if(findNum == arr[i]){
//                System.out.println( findNum +"对应的下标是"+ i);
//                }
//        }
//        long end = System.currentTimeMillis();
//        System.out.println("用时"+ (end - start));

        //二分查找,用时10ms
        long start = System.currentTimeMillis();
        binary_search.binarySearch(arr,0,arr.length - 1,findNum);
        if(binary_search.res == -1){
            System.out.println(findNum + "在数列中不存在");
        }else{
            System.out.println(findNum +"对应的下标是"+ binary_search.res);
        }
        long end = System.currentTimeMillis();
        System.out.println("用时"+ (end - start));

    }
}
class binary_search{
    static int res = -1;
    public static void binarySearch(int[] arr,int left,int right,int key) {
        int mid = (left + right) / 2;
        if (key > arr[right] || key < arr[0]) {
            return ;
        }
        if (left == right) {
            res = left;
            return;
        }
        if(left <= right) {
            if (key > arr[mid]) {
                binarySearch(arr, mid + 1, right, key);
            } else if (key <arr[mid]){
                binarySearch(arr, left, mid - 1, key);
            }else{
                res = mid;
                return;
            }
        }

    }

}